\section{Trabalhos Relacionados}
\label{sec:relacionados}

A predição de disponibilidade de recursos computacionais para auxiliar o escalonamento de tarefas em grades computacionais não é uma idéia nova. Ren~\cite{Ren2006} faz uso de uma cadeia de Markov, onde a probabilidade de transições entre os estados da máquina retorna a predição para o próximo tempo. Ren faz uso de $N$ tempos anteriores para calcular as probabilidades da cadeia de Markov. Para a predição do próximo tempo, o autor obtém uma taxa de erro (menor que 5\%) comparável com o valor encontrado neste trabalho.

Rood~\cite{Rood2007} faz uma caracterização da disponibilidade em grupos simples divididos em 8 categorias, sendo estas: 4 categorias básicas de frequência do número de transições, ou seja, a frequência que o recurso costuma ficar indisponível, cruzadas com 2 categorias com o tipo de transição de estado (abrupta ou suave). A importância do tipo de transição existe em especial para o Condor, que permite a execução de checkpoint durante uma transição suave. O foco deste trabalho de Rood é uma avaliação deste resultado no escalonamento, e não tanto na qualidade da predição (i.e. se uma caracterização passada é eficiente no futuro).


Andrzejak~\cite{Andrzejak2008} é o primeiro autor que faz uso de uma técnica de aprendizado de máquina através de redes bayesianas avaliando diversas janelas de predição. Para uma janela de predição de 2 horas, o trabalho de Andrzejak apresenta uma taxa de erro compatível com este trabalho, um valor inferior a 5\%. Ainda, avaliou que o grande sucesso de predição ocorre pela alta disponibilidade continua das máquinas, o que justifica o maior sucesso da técnica de predição simples que foi apresentada anteriormente.

Já Kondo~\cite{Kondo2008} faz uma classificação por agrupamento semelhante a Rood~\cite{Rood2007}, mas utiliza da técnica de k-means para obter o número de grupos ideais. Kondo não considera transições abruptas ou suaves, apenas tratando da disponibilidade e obtém que 5 grupos são ideais para a classificação de disponibilidade. De relevante para este trabalho, Kondo discute que o estudo do dia da semana e horário do dia de diversas máquinas não são tão relevantes para detectar um padrão de comportamento, devendo o sistema de predição focar em pequenos grupos de máquinas que possam apresentar uma uniformidade de comportamento.

Num trabalho mais recente, Rood~\cite{Rood2009} avaliou a técnica de Ren, expandindo para outras técnicas de predição. Das técnicas avaliados, o mais próximo deste trabalho é o N-Recent. Nesta técnica, são usadas $N$ passadas para a predição das $N$ horas futuras. Esta técnica se aproxima da técnica de predição simples apresentada, na medida em que são consideradas apenas as predições de tarefas de curta duração (1 hora). Assim, 1-Recent equivale a técnica de predição simples e é capaz de apresentar os melhores resultados de outras técnicas de predição como a de Ren ou uso de modelos lineares de regressão. Novamente, o resultado apresentado por Rood se aproxima da taxa de erro encontrada neste trabalho (menor que 5\%).

Todos os trabalhos avaliam o impacto da predição no escalonamento de tarefas e apresentam uma melhoria de desempenho e tempo de resposta em todos os cenários avaliados.